﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetcodeTest._100._10
{
    public class Leetcode4
    {
        public void Test()
        {
            try
            {
                int[] nums1 = new int[] {  };
                int[] nums2 = new int[] { 2 ,3};
                FindMedianSortedArrays(nums1, nums2);
            }
            catch (Exception ex)
            { }
        }

        /*
         4. Median of Two Sorted Arrays
         There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).


            Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

             */
        public double FindMedianSortedArrays(int[] nums1, int[] nums2)
        {
            double dRet = 0;
            int totalLength = nums1.Length + nums2.Length;
            int lastIndex = lastIndex = totalLength / 2;
            bool isOdd = true;
            if (totalLength % 2 == 0)
            {
                isOdd = false;
            }
            List<int> list = new List<int>();
            int breakIndex = 0;
            int i = 0, j = 0;
            if (nums1 == null || nums1.Length == 0)
            {
                breakIndex = 2;
            }
            else if (nums2 == null || nums2.Length == 0)
            {
                breakIndex = 3;
            }
            else
            {
                for (; i < nums1.Length && j < nums2.Length;)
                {
                    if (list.Count - 1 == lastIndex)
                    {
                        breakIndex = 1;
                        break;
                    }
                    if (nums1[i] <= nums2[j])
                    {
                        list.Add(nums1[i]);

                        i++;
                        if (i == nums1.Length)
                        {
                            breakIndex = 2;
                            break;
                        }
                    }
                    else
                    {
                        list.Add(nums2[j]);
                        j++;
                        if (j == nums2.Length)
                        {
                            breakIndex = 3;
                            break;
                        }
                    }
                }
            }

            switch (breakIndex)
            {
                case 1:
                    break;
                case 2:
                    for (; j < nums2.Length; j++)
                    {
                        list.Add(nums2[j]);
                        if (list.Count - 1 == lastIndex)
                        {
                            break;
                        }
                    }
                    break;
                case 3:
                    for (; i < nums1.Length; i++)
                    {
                        list.Add(nums1[i]);
                        if (list.Count - 1 == lastIndex)
                        {
                            break;
                        }
                    }
                    break;
            }


            if (!isOdd)
            {
                dRet = (list[lastIndex] + list[lastIndex - 1]) / 2.0;
            }
            else
            {
                dRet = list[lastIndex];
            }

            return dRet;
        }
    }
}
